摘要 :
The editor in chief rings in the new year by describing the various changes he's implemented for 2007, including adding new department editors, changing department titles, and starting a new horizontal track to cover the Internati...
展开
The editor in chief rings in the new year by describing the various changes he's implemented for 2007, including adding new department editors, changing department titles, and starting a new horizontal track to cover the International Polar Year. Special thanks is extended to those reviewers who contributed to the magazine in 2006.
收起
摘要 :
The editor in chief describes how the conferences he's attended so far this year will affect our editorial calendar offerings in the latter half of 2007.
摘要 :
Associate editor in chief, Denis Donnelly, invited two luminaries from different institutions to discuss the role of computation in science and engineering.
摘要 :
Many of today's students barely know what a desktop computer is, much less want to focus their studies on the traditional computer science curriculum. Instead, professors should consider a cross-disciplinary approach that crosses ...
展开
Many of today's students barely know what a desktop computer is, much less want to focus their studies on the traditional computer science curriculum. Instead, professors should consider a cross-disciplinary approach that crosses fences and helps students learn what's behind the networked world they live in.
收起
摘要 :
The question of whether there is a logic that captures polynomial time is oneof the main open problems in descriptive complexity theory and database theory.In 2010 Grohe showed that fixed point logic with counting captures polynom...
展开
The question of whether there is a logic that captures polynomial time is oneof the main open problems in descriptive complexity theory and database theory.In 2010 Grohe showed that fixed point logic with counting captures polynomialtime on all classes of graphs with excluded minors. We now consider classes ofgraphs with excluded induced subgraphs. For such graph classes, an effectivegraph decomposition, called modular decomposition, was introduced by Gallai in1976. The graphs that are non-decomposable with respect to modulardecomposition are called prime. We present a tool, the Modular DecompositionTheorem, that reduces (definable) canonization of a graph class C to(definable) canonization of the class of prime graphs of C that are coloredwith binary relations on a linearly ordered set. By an application of theModular Decomposition Theorem, we show that fixed point logic with countingcaptures polynomial time on the class of permutation graphs. Within the proofof the Modular Decomposition Theorem, we show that the modular decomposition ofa graph is definable in symmetric transitive closure logic with counting. Weobtain that the modular decomposition tree is computable in logarithmic space.It follows that cograph recognition and cograph canonization is computable inlogarithmic space.
收起
摘要 :
The success of human civilization is rooted in our ability to cooperate by communicating and making joint plans. We study how artificial agents may use communication to better cooperate in Diplomacy, a long-standing AI challenge. ...
展开
The success of human civilization is rooted in our ability to cooperate by communicating and making joint plans. We study how artificial agents may use communication to better cooperate in Diplomacy, a long-standing AI challenge. We propose negotiation algorithms allowing agents to agree on contracts regarding joint plans, and show they outperform agents lacking this ability. For humans, misleading others about our intentions forms a barrier to cooperation. Diplomacy requires reasoning about our opponents’ future plans, enabling us to study broken commitments between agents and the conditions for honest cooperation. We find that artificial agents face a similar problem as humans: communities of communicating agents are susceptible to peers who deviate from agreements. To defend against this, we show that the inclination to sanction peers who break contracts dramatically reduces the advantage of such deviators. Hence, sanctioning helps foster mostly truthful communication, despite conditions that initially favor deviations from agreements.
收起
摘要 :
We study multiplayer quantitative reachability games played on a finitedirected graph, where the objective of each player is to reach his target setof vertices as quickly as possible. Instead of the well-known notion of Nashequili...
展开
We study multiplayer quantitative reachability games played on a finitedirected graph, where the objective of each player is to reach his target setof vertices as quickly as possible. Instead of the well-known notion of Nashequilibrium (NE), we focus on the notion of subgame perfect equilibrium (SPE),a refinement of NE well-suited in the framework of games played on graphs. Itis known that there always exists an SPE in quantitative reachability games andthat the constrained existence problem is decidable. We here prove that thisproblem is PSPACE-complete. To obtain this result, we propose a new algorithmthat iteratively builds a set of constraints characterizing the set of SPEoutcomes in quantitative reachability games. This set of constraints isobtained by iterating an operator that reinforces the constraints up toobtaining a fixpoint. With this fixpoint, the set of SPE outcomes can berepresented by a finite graph of size at most exponential. A careful inspectionof the computation allows us to establish PSPACE membership.
收起
摘要 :
The statistics show that the number of Computer Science majors is dropping across the United States. Possible reasons include a reduced number of jobs in the field, an incorrect perception of what Computer Scientists do, and the s...
展开
The statistics show that the number of Computer Science majors is dropping across the United States. Possible reasons include a reduced number of jobs in the field, an incorrect perception of what Computer Scientists do, and the students' disinterest due to a lack of familiarity with the subject. The reasons may be different for males and females. This paper reports on a study in which 836 high school calculus and pre-calculus students were surveyed to try to determine why students with an apparent aptitude for CS did not pursue a major in Computer Science. The results supported some of the hypotheses for declining enrollment, and rejected others. The top reasons for rejecting the major were the same for both genders, but the reasons for choosing the major differed.
收起
摘要 :
Background and Context: EarSketch was developed as a program to foster persistence in computer science with diverse student populations. Objective: To test the effectiveness of EarSketch in promoting intentions to persist, particu...
展开
Background and Context: EarSketch was developed as a program to foster persistence in computer science with diverse student populations. Objective: To test the effectiveness of EarSketch in promoting intentions to persist, particularly among female students and under-represented minority students. Method: Meta-analyses, structural equation modeling, multilevel modeling, and qualitative analyses were performed to examine how participation in EarSketch and other factors affect students' intentions to persist in computing. Findings: Students significantly increased their intentions to persist in computing, g = .40[.25,54], but examination within just the five quasi-experimental studies did not result in a significant difference for students in EarSketch compared to students not in EarSketch, g = .08[-.07, .23]. Student attitudes towards computing and the perceived authenticity of the EarSketch environment significantly predicted intentions to persist in computing. Implications: Participation in computer science education can increase students' intentions to persist in programming, and EarSketch is one such program that can aid in these intentions.
收起
摘要 :
This special session examines frameworks for the preparation of high school computer science (CS) teachers from the Israeli perspective. Specifically, several Israeli CS teacher preparation programs and their components are presen...
展开
This special session examines frameworks for the preparation of high school computer science (CS) teachers from the Israeli perspective. Specifically, several Israeli CS teacher preparation programs and their components are presented. The presentation includes both a general overview and a detailed description of the actual implementation of such programs. This bipolar presentation, we suggest, provides practical guidelines with respect to CS teacher preparation, both for policy makers and for faculty members who wish to establish a CS teacher preparation program at their universities.
收起
